home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 13742 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.9 KB
  1. Path: news.iadfw.net!usenet
  2. From: Mark Nelson <markn@airmail.net>
  3. Newsgroups: comp.lang.c
  4. Subject: Re: fast find algorithm
  5. Date: Tue, 09 Apr 1996 22:12:22 -0500
  6. Organization: Guest user
  7. Message-ID: <316B2716.4993@airmail.net>
  8. References: <Dp8wE6.8DG@cix.compulink.co.uk> <PdvZxMlyZE9U088yn@ime.usp.br> <4k9ggs$4ov@news1.mnsinc.com> <4kbrg8$luu@druid.borland.com>
  9. NNTP-Posting-Host: dal13-04.ppp.iadfw.net
  10. Mime-Version: 1.0
  11. Content-Type: text/plain; charset=us-ascii
  12. Content-Transfer-Encoding: 7bit
  13. X-Mailer: Mozilla 2.0GoldB2 (Win95; I)
  14.  
  15. Pete Becker wrote:
  16. > 
  17. > In article <4k9ggs$4ov@news1.mnsinc.com>, huang@mnsinc.com says...
  18. > >
  19. > >Rogerio Brito (rbrito@ime.usp.br) wrote:
  20. > >: huang@mnsinc.com (Szu-Wen Huang) wrote:
  21. > >: >Falstaff (falstaff@xs4all.nl) wrote:
  22. > >: >...
  23. > >: >: Hashing is slightly slower than straight table lookup and can't be
  24. > >: >: used when you want to delete elements from your table.
  25. > >: >...
  26. > >
  27. > >: >Hashing can't be used when you want to delete elements?  Please explain.
  28. > >
  29. >     It depends on what you use to resolve conflicting hash values for different
  30. > elements. If you resolve conflicts by rehashing, or by moving to the next
  31. > available entry in the hash array, or any other mechanism that uses the array
  32. > itself as the storage location for the conflicting value, then you can't delete
  33. > items, cause once you do there's no way to get to the ones that used to
  34. > conflict. The first one you try will map to your now-empty location, and it'll
  35. > look like it wasn't found.
  36. >     If you use a linked list at each array location to resolve conflicts then
  37. > you can delete elements.
  38.  
  39. Knuth gives an algorithm for deleting elements from a table when using linear probing, 
  40. and it's pretty easy to see how that would work.  I'm not sure there is a practical 
  41. way to remove elements when using a secondary hash probe...
  42.  
  43. Mark Nelson
  44. http://web2.airmail.net/markn
  45.